#ifndef RADIX_H
#define RADIX_H
#include <stdint.h>
#include <stddef.h>

#define RAX_NODE_MAX_SIZE ((1 << 29) - 1)

typedef struct raxNode
{
    uint32_t iskey : 1;   /* Does this node contain a key? */
    uint32_t isnull : 1;  /* Associated value is NULL (don't store it). */
    uint32_t iscompr : 1; /* Node is compressed. */
    uint32_t size : 29;   /* Number of children, or compressed string len. */
    unsigned char *data;
} raxNode;

typedef struct rax
{
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

#define RAX_STACK_STATIC_ITMES 32
typedef struct raxStack
{
    void **stack;
    size_t items, maxitems;
    void *static_items[RAX_STACK_STATIC_ITMES];
    int oom;
} raxStack;

typedef int (*raxNodeCallback)(raxNode **noderef);

#define RAX_ITER_STATIC_LEN 128
#define RAX_ITER_JUST_SEEKED (1 << 0)
#define RAX_ITER_EOF (1 << 1)
#define RAX_ITER_SAFE (1 << 2)

typedef struct raxIterator
{
    int flags;
    rax *rt;            /* Radix tree we are iterating. */
    unsigned char *key; /* The crurrent string. */
    void *data;         /* Data associated to this key. */
    size_t key_len;     /* Current key length. */
    size_t key_max;     /* Max key len the current key buffer can hold. */
    unsigned char key_static_string[RAX_ITER_STATIC_LEN];
    raxNode *node;           /* Current node. Only for unsafe interation. */
    raxStack stack;          /* Stack used for unsafe iteration. */
    raxNodeCallback node_cb; /* Optional node callback. Normally set to NULL. */
} raxIterator;

extern void *raxNotFound;

/* Exported API */
rax *raxNew(void);
int raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
int raxTryInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
int raxRemove(rax *rax, unsigned char *s, size_t len, void **old);
void *raxFind(rax *rax, unsigned char *s, size_t len);
void raxFree(rax *rax);
void raxFreeWithCallback(rax *rax, void (*free_callback)(void *));
void raxStart(raxIterator *it, rax *rt);
int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len);
int raxNext(raxIterator *it);
int raxPrev(raxIterator *it);
int raxRandomWalk(raxIterator *it, size_t steps);
int raxCompare(raxIterator *iter, const char *op, unsigned char *key, size_t key_len);
void raxStop(raxIterator *it);
int raxEOF(raxIterator *it);
void raxShow(rax *rax);
uint64_t raxSize(rax *rax);
unsigned long raxTouch(raxNode *n);
void raxSetDebugMsg(int onoff);

/* Internal API. May be used by the node callback in order to access rax node
   in a low level way, so this function is exported as well.*/
void raxSetData(raxNode *n, void *data);
#endif